package problems.practice;

import java.util.Arrays;

/**
 * 532. 数组中的 k-diff 数对
 * <p>https://leetcode.cn/submissions/detail/368038236/</p>
 */
public class T532 {
    public int findPairs(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k < 0) return 0;

        Arrays.sort(nums);

        int n = nums.length;
        int ret = 0;

        for (int i = 0; i < n; ++i) {
            // 排除重复计算
            if (i > 0 && nums[i] == nums[i-1]) continue;

            if (i > 0 && nums[i] - nums[0] >= k)
                // 向左寻找
                ret += findPair(nums, 0, i - 1, nums[i] + k) ? 1 : 0;
            if (i < n - 1 && nums[n-1] - nums[i] >= k) {
                // 向右寻找
                ret += findPair(nums, i + 1, n - 1, nums[i] + k) ? 1 : 0;
            }
        }

        return ret;

    }

    private boolean findPair(int[] nums, int l, int r, int target) {
        int m;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (nums[m] > target) r = m - 1;
            else if (nums[m] < target) l = m + 1;
            else return true;
        }

        return false;
    }
}
